#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define MAP_SIZE	(128)
#define PATH_SIZE	(1024)
#define GBLOCK		(-1)

#define CLR()           printf("\033[2J")
#define GOTOXY(x, y)    printf("\033[%d;%dH", (y)+1, (x)+1)
#define	XY2V(x, y, v)	do{										\
							(v) = ((unsigned int)(y) << 16)		\
							+ (unsigned int)(x);				\
						}while(0)
#define	V2XY(x, y, v)	do{										\
							(y) = (unsigned short)((v) >> 16); 	\
							(x) = (unsigned short)(v);			\
						}while(0)

//f(n) = g(n) + h(n)

typedef struct vex{
	short x;
	short y;
	int f;
	unsigned int parent;
	struct vex * next;
} vex;

//OPEN queue head
vex openq;
//path
unsigned int path[PATH_SIZE];

//read map
char map[MAP_SIZE][MAP_SIZE];

//CLOSED
//g map
short gmap[MAP_SIZE][MAP_SIZE];


short map_w,map_h;
short start_x,start_y,end_x,end_y;

//h func
short hfunc(short x, short y)
{
	return abs(x - end_x) + abs(y - end_y);
}

//small -> big
//queue func
int enq(short x, short y, short px, short py)
{
	vex * v = (vex *)malloc(sizeof(vex));
	v->x = x;
	v->y = y;
	v->f = gmap[y][x] + hfunc(x, y);
	XY2V(px, py, v->parent);
	vex * p = &openq;
	while(p->next && p->next->f < v->f){
		p = p->next;
	}
	v->next = p->next;
	p->next = v;
	return 0;
}

vex * deq()
{
	vex * v = openq.next;
	if(v){
		openq.next = v->next;
	}
	return v;
}

int line = 0;
int move(int x, int y, vex * p)
{
	//if blocked, return
	if(map[y][x] != ' ' && map[y][x] != 'e'){
		return 1;
	}
	if(gmap[p->y][p->x] == GBLOCK){
		return 1;
	}
	//if better visited, return; else set gmap
	if(gmap[y][x] <= gmap[p->y][p->x] + 1 ){
		return 1;
	}else{
		gmap[y][x] = gmap[p->y][p->x] + 1;
	}
	//addsort openq
#ifdef DETAIL
	GOTOXY(x, y);
	getchar();
	line = 0;
#endif
	enq(x, y, p->x, p->y);
	return 0;
}

int astar()
{
	//init path
	memset(path, 0, sizeof(path));
	//init g map
	int i;
	for(i = 1; i < MAP_SIZE * MAP_SIZE; i ++){
		*((short *)gmap + i) = PATH_SIZE;
	}
	gmap[start_y][start_x] = 0;
	//init open queue
	openq.next = NULL;
	enq(start_x, start_y, 0, 0);
	
	while(1){
		vex * p = deq();
		if(!p){
			return 1;
		}
		//push path
		short g = gmap[p->y][p->x];
		assert(g < PATH_SIZE);
//		XY2V(p->x, p->y, path[g]);
		if(p->parent){
			assert(g != 0);
			path[g - 1] = p->parent;
		}
#ifdef DETAIL
		GOTOXY(p->x, p->y);
		printf(".");
		if(p->parent){
			int a,b;
			V2XY(a,b,p->parent);
			GOTOXY(a, b);
			printf("*");
		}
		GOTOXY(0, map_h+line);
		printf("x: %d, y: %d\n", p->x, p->y);
		fflush(stdout);
#endif
		
		if(p->x == end_x && p->y == end_y){
			return 0;
		}

		int ret = move(p->x, p->y-1, p);	//up
		ret &= move(p->x, p->y+1, p);		//down
		ret &= move(p->x-1, p->y, p);		//left
		ret &= move(p->x+1, p->y, p);		//right
		//all failed, block
		if(ret){
			gmap[p->y][p->x] = GBLOCK;
		}
	}
}

//show path
int show_path()
{
	int i;
	for(i = 0; i < PATH_SIZE; i ++){
		if(path[i] == 0){
			break;
		}
		short x, y;
		V2XY(x, y, path[i]);
		GOTOXY(x, y);
		if(map[y][x] == 's'){
			printf("s");
		}else if(map[y][x] == 'e'){
			printf("e");
		}else{
			printf("-");
		}
	}
	return 0;
}

//read map
int read_map(const char * file)
{
	FILE * f = fopen(file, "r");
	if(f == NULL){
		return -1;
	}
	if(fscanf(f, "%hd,%hd\n", &map_w, &map_h) != 2){
		return -2;
	}
	printf("no way %d, %d\n", map_w, map_h);
	assert(map_w < MAP_SIZE && map_h < MAP_SIZE);
	int i, j;
	start_x = start_y = end_x = end_y = -1;
	for(i = 0; i < map_h; i ++){
		fgets(map[i], map_w + 1, f);
		for(j = 0; j < map_w; j ++){
			if(map[i][j] == 's'){
				start_x = j;
				start_y = i;
			}else if(map[i][j] == 'e'){
				end_x = j;
				end_y = i;
			}
		}
	}
	assert(start_x > -1 && end_x > -1);
	fclose(f);
	return 0;
}

//show map
int show_map()
{
	CLR();
	GOTOXY(0, 0);
	int i;
	for(i = 0; i < map_h; i ++){
		fputs(map[i], stdout);
	}
	return 0;
}

int main()
{
	read_map("map.dat");
	show_map();
	getchar();
	if(astar() > 0){
		GOTOXY(0, map_h);
		printf("no way %d, %d\n", map_w, map_h);
		return 1;
	}
	show_path();
	GOTOXY(0, map_h);
	return 0;
}

